# 第3节层层递进——广度优先搜索
class Note:

    def __init__(self, x, y, s):
        self.x = x
        self.y = y
        self.f = 0
        self.s = s


# n = Note(0, 0, 0)
# print(n)
# print(id(n))
que = [Note(0, 0, 0) for i in range(1, 2501)]
# que = [Note(0, 0, 0)] * 3 # 请勿使用浅拷贝
# print(que)
head = 1
tail = 1
# 地图
a = [[0 for i in range(51)] for j in range(51)]
# print(a)
# 标记哪些点已经记录到队列中
book = [[0 for i in range(51)] for j in range(51)]
# 第一步将(1,1)加入队列，并标记(1,1)已经走过
que[tail].x = 1
que[tail].y = 1
que[tail].s = 0
que[tail].f = 0
tail += 1
book[1][1] = 1
# 下一步 右 下 坐 上
next_array = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# 小哈的坐标
p = 4
q = 3

n = 5  # 行数
m = 4  # 列数

a = [[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 1],
     [0, 1, 1, 4, 3]]

flag = 0  # flag=0 ; 1用来标记是否到达目标点，0表示哲时还没有到达。1表示到达当队列不为空的时循环
while head < tail:
    # 枚举四种走法
    for k, v in enumerate(range(0, 4)):
        # print(k)
        # print(k)
        # 计算下一个坐标
        tx = que[head].x + next_array[k][0]
        ty = que[head].y + next_array[k][1]
        # 判断是否越界
        if tx < 1 or tx > n or ty < 1 or ty > m:
            continue
        if a[tx][ty] == 0 and book[tx][ty] == 0:
            book[tx][ty] = 1
            que[tail].x = tx
            que[tail].y = ty
            que[tail].f = head
            que[tail].s = que[head].s + 1
            tail += 1
        # 到达目标
        if tx == p and ty == q:
            flag = 1
            break
    if flag == 1:
        break
    head += 1  # 一个点结束后进行下一个点

print(que[tail - 1].s)

print(que)